For transmitting information over a telecommunications channel, digital information is typically coded and transmitted in the form of code words. An exemplary binary encoding method with a substantially uniform rate is described in U.S. Pat. No. 5,300,930. It is often desirable to encode the digital information using as few bits as possible in order to minimize the bandwidth required. Depending on the probability distribution of the events described by the digital information, the information can be encoded such that events that occur rarely are coded with longer code words and events that occur frequently are coded with shorter code words. The encoding is preferably done in such a manner that the decoder can distinguish between the different code words.
However, a typical transmission channel between a transmitter and a receiver introduces bit errors, and it is difficult for the decoder (at the receiver) to reliably decode the different variable length code words because the encoder cannot determine where one code word starts and another ends. Usually this problem is solved by channel coding, where controlled repetition or redundancy is introduced by the channel encoder. The repetition of code words enables the channel decoder to detect and correct erroneous bits.
Using this method, more bits have to be transmitted over the channel. The channel bit rate increases, and the channel encoder and decoder must necessarily be more complex. Moreover, at bit error rates higher than the error correcting capacity of the channel coding, the decoded bit error rate often becomes worse than the uncoded bit error rate. Such a threshold bit error rate exists for every code, based on either the Shannon capacity formula or on a restriction in acceptable delay due to channel coding.
A fixed length code overcomes some of the disadvantages of a variable length code, in terms of bit error robustness. While some efficiency is lost because all code words have the same length independent of the probability distribution of the information to be coded, each code word can be decoded independent of any other code word once synchronization is achieved.
To implement a fixed length coding scheme, the information to be transmitted is assumed to represent a `level curve` monotonically increasing from a minimum value to a maximum value. The events described by the information represent discrete points on this level curve and each point is coded with a fixed length code word. A bit error in a code word causes a jump in the level curve the magnitude of which depends on which bit in the code word is erroneous. This means that some bit errors (at certain positions in the code word) may result in an acceptable decoded level (small level error) while other error bits in a code word results in a totally unacceptable level change.
A recommended standard for Very Low Bitrate Video Telephony over a mobile channel is currently being developed. According to current proposals for the standard, two 8-bits fixed length code tables provide essentially a `straight forward` code, such that the index of the level function is represented as a binary value and used as a code word. It would be desirable to improve the error robustness of the fixed length code tables in video telephony applications. It would further be desirable to design a code table with a gain in mean squared error (mse) (compared to the `straight forward code`) for probability density functions (pdfs) having a rather sharp peak, since the chrominance (color difference) components represented by the fixed length tables usually have a very pronounced peak.
It is known to improve fixed length code robustness to bit errors by means of Gray coding, which can be described in detail in the following references: John A. G. Bingham, "The Theory and Practice of Modem Design", John Wiley & Sons, 1988 (pp. 65-66); and E. A. Lee, D. G. Messerschmitt, "Digital Communication", Kluwer Academic Publishers Boston, 1988 (p. 193).
Gray codes have the property that adjacent data are encoded into code words that differ by only one bit, i.e. the Hamming distance is 1. This is particularly effective for a 2-bit code (4 words) in a 2-dimensional signal constellation, where the Euclidean distance is at a minimum for code words with Hamming distance=1, as in FIG. 1.
In a 1-dimensional representation, when each code word represents a level, the result is different, as illustrated with the following 3-bit codes with 8 levels. A straight code and two Gray codes with associated bit error distances are shown in Table 1. The distance d1 is the sum of the distances obtained by changing one bit at a time in the code word. The mean distance per bit is then d1/3 units.
TABLE 1 ______________________________________ Straight Code Gray Code 1 Gray Code 2 Level Code Distance d1 Code Distance d1 Code Distance d1 ______________________________________ 0 000 4+2+1=7 000 5+1+3=9 000 3+1+7=11 1 001 4+2+1=7 010 5+1+1=7 010 1+1+5=7 2 010 4+2+1=7 011 5+1+1=7 110 1+1+3=7 3 011 4+2+1=7 001 1+1+3=5 100 3+1+1=5 4 100 4+2+1=7 101 1+3+1=5 101 3+1+1=5 5 101 4+2+1=7 100 5+1+1=7 111 1+1+3=5 6 110 4+2+1=7 110 5+1+1=7 011 1+1+5=7 7 111 4+2+1=7 111 5+3+1=9 001 3+1+7=11 ______________________________________
Using a metric based upon the Euclidean distance, d1, or the squared Euclidean distance, d2, the following distances can be defined: ##EQU1## where n is the number of bits in each fixed-length code word,
M is the number of fixed length code words, PA1 p(m) is the pdf of the level, m=0, 1, . . . , M-1, PA1 .epsilon.1 is the mean error distance per bit and PA1 .epsilon.2 is the mean squared distance (mse) per bit.
The mean error distance per bit is .epsilon.1=7/3=2.33 units for all three codes in Table 1. Thus, for a uniform pdf, a Gray code offers no advantages over a straight code. However, if the levels 3 and 4 (2, 3, 4 and 5) are more common than the other levels, the Gray code 1 (Gray code 2) results in an increased mean error distance.
If a bit error is introduced in the straight code in Table 1, the level jump may be 1, 2 or 4 units depending on the position of the erroneous bit. This is valid for each of the 8 code words and the mean error distance is .epsilon.1=7/3=2.33 units per bit. If the mse is used, the result becomes .epsilon.2=(1.sup.2 +2.sup.2 +4.sup.2)/3=7 units.sup.2 per bit. These values .epsilon.1 and .epsilon.2 are independent of the actual pdf, and therefore this straight code may serve as a reference for other codes.
Assuming a uniform pdf for the Gray code 1 we get a mean error distance of .epsilon.1=2*(9+7+7+5)/(8*3)=7/3=2.33 units per bit which is equal to the straight coding. The mse becomes .epsilon.2=25/3=8.33 units.sup.2 per bit.
The corresponding figures for the Gray code 2 are; mean error distance .epsilon.1=7/3=2.33 units per bit and mse .epsilon.2=27/3=9 units.sup.2 per bit.
Thus, nothing is gained by using a Gray code instead of a straight code if the level pdf is uniform. In fact, if mse is chosen as the metric there is a performance loss.
However, if a pdf has a peak in the central part of the coding table a performance gain can be achieved by the Gray code tables.
Still, the minimum distance and the minimum squared distance are for the Gray code tables 5/3=1.67 units per bit and 11/3=3.67 units.sup.2 per bit , respectively, and these values may be too large to be acceptable. Further, these values do not represent the minimum values that can be achieved.
It will be appreciated that sometimes a pdf does not have a peak at a central location, and may instead be of a more general shape having two or more peaks on either side of the center of the level curve.
It would therefore be desirable for a coding scheme to provide a robust, fixed-length code for encoding information having a non-uniform probability density function; that is, a pdf having a peak. It would also be desirable for a coding scheme to provide a robust, fixed-length code for encoding information having a more general pdf; that is, a pdf having multiple peaks.